package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/target-sum/
 * @create 2025/9/1 18:27
 * @since JDK17
 */

public class Solution43 {
    public int f(int[] nums, int t) {
        int n = nums.length;
        int[] dp = new int[t + 1];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = t; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[t];
    }
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length, sum = Arrays.stream(nums).sum();
        if (sum < Math.abs(target) || sum % 2 != target % 2) {
            return 0;
        }
        return f(nums, (target + sum) / 2);
    }
}
